The present invention relates to communications and more particularly to cache management for supporting communications.
The Internet is a worldwide decentralized network of computers having the ability to communicate with each other. The Internet has gained broad recognition as a viable medium for communicating and interacting across multiple networks. The World-Wide Web (Web) was created in the early 1990""s, and is comprised of server-hosting computers (Web servers) connected to the Internet that have hypertext documents (referred to as Web pages) stored therewithin. Web pages are accessible by client programs (e.g., Web browsers) utilizing the Hypertext Transfer Protocol (HTTP) via a Transmission Control Protocol/Internet Protocol (TCP/IP) connection between a client-hosting device and a server-hosting device. While HTTP and hypertext documents are the prevalent forms for the Web, the Web itself refers to a wide range of protocols including Secure Hypertext Transfer Protocol (HTTPS), File Transfer Protocol (FTP), and Gopher, and content formats including plain text, Extensible Markup Language (XML), as well as image formats such as Graphics Interchange Format (GIF) and Joint Photographic Experts Group (JPEG).
An intranet is a private computer network conventionally contained within an enterprise and that conventionally includes one or more servers in communication with multiple user computers. An intranet may be comprised of interlinked local area networks and may also use leased-lines in a wide-area network. An intranet may or may not include connections to the outside Internet. Intranets conventionally utilize various Internet protocols and, in general, often look like private versions of the Internet. An intranet user conventionally accesses an intranet server via a Web browser running locally on his/her computer.
As is known to those skilled in this art, a Web page is conventionally formatted via a standard page description language such as HyperText Markup Language (HTML), which typically contains text and can reference graphics, sound, animation, and video data. HTML provides for basic document formatting and allows a Web content provider to specify anchors or hypertext links (typically manifested as highlighted text) to other Web servers and files. When a user selects a particular hypertext link, a Web browser reads and interprets an address, called a Uniform Resource Locator (URL) associated with the link, connects the Web browser with a Web server at that address, and makes a request (e.g., an HTTP request) for the file identified in the link. The Web server then sends the requested file to the Web client which the Web browser interprets and displays to the user.
In communications between a client and a server, such as over the Internet, and in other applications involving transfers of large amounts of information over a communication channel, it is often desireable to improve the performance of the communication channel by reducing the volume of data which must be transferred. One known approach takes advantage of the fact that some communications contain redundant information, in other words, information which was previously communicated between a client and a server which has not changed in the time between the previous request initiating a transfer and a subsequent new request for the same information. For example, a Web browser may request a file with a particular associated URL address on multiple occasions. Various approaches using caches have been proposed which are intended to recognize when requested information is already available to the requesting device in a local cache. The web browser is then provided the locally available portion of the requested information from the local cache and only new information is transmitted to the requesting client over the communication channel.
An example of such a cache management system that provides for management of the contents of the cache to control the amount of memory required to support the cache is described in Charu Aggarwal, et al., xe2x80x9cCaching on the World Wide Webxe2x80x9d, IEEE Transactions on Knowledge and Data Engineering, January/February 1999. As described in this article, HTTP caches suffer from the fact that a large number of requests they serve are for objects which will never be requested again before they expire. A proposed solution from the article is a cache admittance protocol which uses a second cache containing only the URLs which have been requested. The actual object would then be cached when a certain frequency of reference to the object has been seen by the cache.
One problem with the approach described in Aggarwal is the amount of storage required. The URLs typically take up approximately 0.3% of the size of the actual objects. Furthermore, it has been suggested that the URL cache should have a capacity (in number of objects) twice as large as the cache used for actual objectsxe2x80x94or about 0.6% of total cache size. As object caches for modem HTTP caches are on the order of 100 gigabytes, this would require about 600 megabytes of storage for the URL cache. Using this approach and given the present hardware capabilities of typical existing equipment, the resulting URL cache generally has to be stored in a secondary storage device as opposed to main memory storage. This typically imposes a performance penalty as the URL cache is accessed and updated very frequently. It is expected, in a typical application, that approximately 50-70% of requests will not be served from the object cache and will, therefore, require accessing and updating the URL cache. A further problem of the protocol suggested in Aggarwal results from the nature of typical World Wide Web traffic. A significant percentage, generally at least 40%, of the bandwidth of a communication channel used for HTTP traffic is for large objects (100 kilobytes and larger) which are accessed very infrequently compared to smaller objects. As a result of the less frequent access to large objects, the Aggarwall cache admittance protocol will make it less likely for those objects to be cached, further reducing the effectiveness of the cache by not providing cache support at a desired level as larger objects tend to take up a significant amount of communication channel bandwidth for transmission. For a further discussion of cache management systems such as those described in Aggarwall, reference is made to U.S. Pat. No. 5,924,116 entitled xe2x80x9cCollaborative Caching of a Requested Object by a Lower Level Node as a Function of the Caching Status of the Object at a Higher Level Nodexe2x80x9d which is incorporated herein by reference as if set forth in its entirety.
It has also been proposed in U.S. Pat. No. 5,864,852 entitled xe2x80x9cProxy Server Caching Mechanism That Provides a File Directory Structure and a Mapping Mechanism Within the File Directory Structurexe2x80x9d (xe2x80x9cthe ""852 patentxe2x80x9d) to use hashing to compress URLs to a fraction of their length. The compressed address is then used as a key for retrieving an associated object. However, the proposal of the ""852 patent still stores the entire URL to check for collisions in an attempt to avoid errors as the proposal relates to object retrieval rather than admission control for a cache.
In light of the above discussion, a need exists for improvements in cache management protocols.
In view of the above discussion, it is an object of the present invention to provide methods, systems and computer program products which can provide for cache management with a reduced memory requirement to support the cache management protocol while still providing for improved performance of the supported communication channel.
A further object of the present invention is to provide such methods, systems and computer program products which can provide for a reduced usage of secondary storage devices in support of cache management.
These and other objects of the present invention may be provided by methods, systems and computer program products which take advantage of the fact that overall performance of the cache determines cache effectiveness and, therefore, a cache admittance protocol does not need perfect information, it only needs to be correct enough of the time to provide a significant benefit in the performance of a supported communication channel. Various embodiments of the present invention also take advantage of the nature of communications traffic on the Web.
In a first aspect, the present invention applies a cache admittance protocol based on an address associated with a unit of information (candidate object) which has been requested, such as a URL associated with a particular file. Both an object cache for containing the information to be cached and an address cache for determining whether a particular received unit of information should be stored in the object cache are provided. The address cache, unlike the prior art approaches described above, utilizes a hashed address generated from the address associated with the unit of information. By providing an address cache based on a hashed address of a shorter length than the actual address, the storage requirements of the address cache may be reduced. Preferably, the length of the hashed address is selected so as to allow the address cache to reside in main memory rather than a secondary storage device, thereby providing for improved system performance.
In a further aspect, the present invention applies the cache admittance protocol only to relatively small objects. As the impact of improved communication channel performance can be most readily provided by eliminating the need for large file size transfers which are often redundant information (such as screen layout, format and graphics characteristics provided to a Web browser), large information units are placed in the object cache regardless of the admittance protocol. The admittance protocol is then applied only to smaller information units which may reduce the storage requirements of the address cache by reducing the number of addresses tracked.
In one embodiment of the present invention, a method is provided for cache management including receiving a candidate object for placement in an object cache, the candidate object having an associated address of a first length. The associated address is hashed to provide a hashed address having a second length shorter than the first length. The hashed address is stored in an address cache which is used for controlling admittance to the object cache. Furthermore, the candidate object may be selectively admitted into the object cache responsive to hashed address information in the address cache.
In a further embodiment, the hashed address is stored to provide an address reference count associated with the hashed address and the candidate object is selectively admitted into the object cache if the address reference count associated with the hashed address of the candidate object satisfies a selection criteria. The object cache may be a Hypertext Transport Protocol (HTTP) object cache and the associated address may be a Universal Resource Locator (URL). The second length of the hashed address may be selected to allow the address cache to be maintained in a main memory of a device performing the cache management. The first length may be between about 40 to about 50 bytes and the second length may be about 4 bytes.
In another embodiment of the present invention the step of selectively admitting is preceded by the step of admitting the candidate object into the object cache if a size of the candidate object exceeds a predetermined criterion. The step of selectively admitting is then only performed if the size of the candidate object is no more than the predetermined criterion.
In a further embodiment of the present invention, a method for cache management is provided including receiving a candidate object for placement in an object cache, the candidate object having an associated size. The cache management protocol then determines if the size of the candidate object exceeds a predetermined criterion wherein the predetermined criterion is independent of an object to be replaced by the candidate object. The candidate object is admitted into the object cache responsive to the determining step if the size exceeds the predetermined criterion and submitted to controlled admittance testing responsive to the determining step if the size is less than the predetermined criterion. In one embodiment, the object cache is a Hypertext Transport Protocol (HTTP) object cache and the predetermined criterion is at least about 100 k bytes and, preferably, is about 100 k bytes. The candidate object is preferably only submitted to controlled admittance testing if the size is less than the predetermined criterion.
As will further be appreciated by those of skill in the art, while described above with reference to method aspects, the present invention may be embodied as methods, apparatus/systems and/or computer program products.